package ArithmeticSummary;

public class aa {
    public static void main(String[] args) {
        int j, low, mid, high, temp;
        int[] arr = new int[]{4, 2, 8, 1, 12, 78, 32};
        for (int i = 1; i < arr.length; i++) {
            low = 0;
            high = i - 1;
            temp = arr[i];
            /*找到合适的插入位置high+1，如果中间位置元素
             *比要插入元素大，则查找区域向低半区移动，否
             *则向高半区移动
             */
            while (low <= high) {
                mid = (low + high) / 2;
                if (arr[mid] > temp) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            /*high+1后的元素后移*/
            for (j = i - 1; j >= high + 1; j--) {
                arr[j + 1] = arr[j];
            }
            /*将元素插入到指定位置*/
            arr[j + 1] = temp;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }
}
